package offer_test_20;

import struct.LinkedNode;

//：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，
//即链表的尾结点是倒数第一个结点。例如一个有6个结点的链表，从头结点依次是1,2,3,4，5,6。
//倒数第三个结点就是值为4的结点。
public class fifteen_KthNodeFromEnd {
	public static void main(String[] args) throws Exception {
		LinkedNode head = new LinkedNode();
		LinkedNode second = new LinkedNode();
		LinkedNode third = new LinkedNode();
		LinkedNode four = new LinkedNode();
		LinkedNode five = new LinkedNode();
		LinkedNode six = new LinkedNode();
		head.next = second;
		second.next = third;
		third.next = four;
		four.next = five;
		five.next = six;
		head.data = 1;
		second.data = 2;
		third.data = 3;
		four.data = 4;
		five.data = 5;
		six.data = 6;
//		LinkedNode rs = deleteKthFromEnd(head, 3);
		LinkedNode rs= findKToTail(head, 3);
		while (rs!=null) {
			System.out.println(rs.data);	
				rs=rs.next;
		}
	}

	public static LinkedNode deleteKthFromEnd(LinkedNode firstnode, int k)
			throws Exception {
		if (firstnode == null || k == 0) {
			return null;
		}
		LinkedNode head = firstnode;
		LinkedNode deletenode = firstnode;
//		while (head.next != null && i < k) {
//			head = head.next;
//			i++;
//		}
		for (int i = 0; i < k-1; ++i) {
			if (head.next != null) {
				head = head.next;
			} else {
				return null;
			}
		}
		while (head != null) {
			deletenode = deletenode.next;
			head = head.next;
		}
		return deletenode;
	}

	public static LinkedNode findKToTail(LinkedNode head, int k) {
		if (head == null || k == 0) {
			return null;
		}
		LinkedNode resultNode = null;
		LinkedNode headLinkedNode = head;
		for (int i = 0; i < k-1; ++i) {
			if (headLinkedNode.next != null) {
				headLinkedNode = headLinkedNode.next;
			} else {
				return null;
			}
		}
		resultNode = head;
		while (headLinkedNode != null) {
			resultNode = resultNode.next;
			headLinkedNode = headLinkedNode.next;
		}
		return resultNode;
	}
}
